import tool.ListNode;
import tool.createList;
import tool.listPrint;
import tool.*;

import javax.sound.midi.Soundbank;
import java.util.List;

/**
 * @Description: 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * @Date:Create in 21:45  2022/6/27
 */
public class reverseList0206 {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5};
        ListNode head = createList.create_List(arr);
        listPrint.printListHead(head);
        ListNode res = reverseList2(head);
        System.out.println("**********");
        listPrint.printListHead(res);
    }

    //双指针法
    public static ListNode reverseList1(ListNode head) {
        ListNode cur = head;
        ListNode pre = head;
        ListNode tar = null;

        while(cur != null){

            cur = cur.next;
            pre.next = tar;
            tar = pre;
            pre = cur;
        }
        return tar;
    }

    //递归
    public static ListNode reverseList2(ListNode head) {
//        ListNode pre = null;
        return reverse(null,head);
    }

    private static ListNode reverse(ListNode pre,ListNode cur){
        if(cur == null){
            return pre;
        }
        ListNode temp = null;
        temp = cur.next;
        cur.next = pre;
        return reverse(cur,temp);
    }
}
